This invention relates to the implementation of the cryptographic primitive Oblivious Transfer, i.e. the transfer of at least one secret string/value held by one party to another party so that the another party can make certain use of the private information without being able to learn the full private information itself. One example of its usage is in secure function evaluation (SFE), a method of function evaluation that provides privacy to parties seeking to compute on their private inputs. The invention more specifically addresses a method by which one of a party's two secret values (keys) is made accessible for calculations made by the other party for use in decrypting encrypted parameters associated with the communication of information between the parties, but where the other party cannot learn the other of the two keys.
SFE implementations have been disclosed, e.g. see “Fairplay—A Secure Two-party Computation System” by D. Malkhi, N. Nisan, B. Pinkas and Y. Sella, USENIX 2004. Two-party general secure function evaluation (SFE) allows two parties to evaluate any function on their respective inputs x and y, while maintaining privacy of both x and y. SFE algorithms enable a variety of electronic transactions, previously impossible due to mutual mistrust of participants. Examples include auctions, contract signing, distributed database mining, etc. As computation and communication resources have increased, SFE has become practical. Fairplay is an implementation of generic two-party SFE with malicious players. It demonstrates the feasibility of SFE for many useful functions, represented as circuits of up to about a million gates. Another example of a SFE protocol implementation is “Y Lindell, B Pinkas, N. Smart, ‘Implementing Two-party Computation Efficiently with Security Against Malicious Adversaries’, SCN 2008”.
The use of a garbled circuit (GC) technique for SFE, especially suited for boolean circuits, is described by Yehuda Lindell and Benny Pinkas, “A Proof of Yao's Protocol for Secure Two-Party Computation”, Cryptology ePrint Archive, Report 2004/175, 2004, http://eprint.iacr.org/. One step in the GC technique is the oblivious transfer (OT) of one of the sender's two secret keys to the receiver. This secret key transfer step is normally implemented by public key encryption techniques and is computationally intensive.